import utils.TreeNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/1 9:50
 * @description:
 */
public class Solution99 {
    TreeNode pre;
    TreeNode first;
    TreeNode second;

    public void recoverTree(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    void traverse(TreeNode node) {
        if (node == null) return;  // 递归终止条件：空节点直接返回
        traverse(node.left);  // 中序遍历左子树（左）
        if (pre != null && pre.val > node.val) {
            if (first == null) {
                first = pre;
            }
            second = node;

        }
        pre = node;
        traverse(node.right);
    }

    public static void main(String[] args) {
        Solution99 solution = new Solution99();
        TreeNode root = TreeNode.buildTree(new int[]{3,1,4,-1,-1,2});
        solution.recoverTree(root);
    }

}
